package com.wrial.kind.dp;
/*
 * @Author  Wrial
 * @Date Created in 16:03 2020/8/14
 * @Description
 * 输入: [0,1,0,2,1,0,1,3,2,1,2,1]  输出: 6   lc42
 */

public class CollectRain {
    /**
     * 1.分层法 每次从第一层，第二层逐层统计，因此需要先统计最大的height，然后逐层，从左往右，如果其中一个大于等于当前层，那就从这里开始计数，然后使用temp_sum计算临时水量每遇到大于等于当前层高的值就把temp_sum加到ans中，否则就不算数
     * 2.暴力法 当前i只关心前面最大的和后面最大的(for循环 i-1到0中找lMax i+1到length-1找rMax)，然后取较小值-height[i]就是容量（首尾一定不会有水）
     * 3.动态规划 暴力法中每次循环都要对当前的左右最大墙高要进行计算，因此在动态规划中将当前i对于的左边最高墙和右边最高墙都统计起来
     * 4.双指针 如果左边可信就计算左边，如果右边可信就计算右边
     * 5.栈 可以看做是括号匹配问题  if stack.peek < height[i] 那就pop然后再peek看是否大于pop的元素一直往复，然后将当前height[i] push进去
     * 然后又宽*高就可以算出大小
     */
    /*
    public int trap(int[] height) {
        int ans = 0;
        for (int i = 1; i < height.length - 1; i++) {
            int lMax = 0, rMax = 0;
            //找出左边最高
            for (int j = i - 1; j >= 0; j--) {
                lMax = Math.max(height[j], lMax);
            }
            //找出右边最高
            for (int j = i + 1; j < height.length; j++) {
                rMax = Math.max(height[j], rMax);
            }
            //去较小
            int min = Math.min(lMax, rMax);
            //计算水量
            if (min>height[i]){
                ans += min - height[i];
            }
        }
        return ans;
    }

     */

    /**
     * dp：记录当前i的左最大和右最大（不包含当前值） 就是暴力循环的改进方法（减少内部循环寻找当前i的lMax和rMax的过程）
     */
  /*  public int trap(int[] height) {
        if (height.length == 0) return 0;
        int[] lMaxDp = new int[height.length];
        int[] rMaxDp = new int[height.length];

        for (int i = 1; i < height.length; i++) {
            lMaxDp[i] = Math.max(lMaxDp[i - 1], height[i - 1]);
        }
        for (int i = height.length - 2; i >= 0; i--) {
            rMaxDp[i] = Math.max(rMaxDp[i + 1], height[i + 1]);
        }
        int ans = 0;
        for (int i = 0; i < height.length; i++) {
            int min = Math.min(lMaxDp[i], rMaxDp[i]);
            if (height[i]<min){
                ans += min - height[i];
            }
        }
        return ans;
    }

   */

    /**
     * 双指针：可以从dp看到，存储lMax和rMax只会被用到一个，那可以使用两个指针来代替两个数组吗？使用双指针
     * lMax代表left之前的最大值，rMax代表right之后的最大值
     * 如果lMax<rMax 那就说明lMax对于left来说是可信的，那就计算left位置的积水量，反之，lMax>=rMax 那rMax对于right来说是可信的
     */
    public int trap(int[] height) {
        if (height.length == 0) return 0;
        int left = 0, right = height.length - 1, lMax = 0, rMax = 0;
        int ans = 0;
        for (int i = 0; i < height.length; i++) {
            if (lMax < rMax) {
                ans += Math.max(0, lMax - height[left]);
                lMax = Math.max(lMax, height[left]);
                left++;
            } else {
                ans += Math.max(0, rMax - height[right]);
                rMax = Math.max(rMax, height[right]);
                right--;
            }
        }
        return ans;
    }
}
